{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Moves to Move a Box to Their Target Location"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minPushBox"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #推箱子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。</p>\n",
    "\n",
    "<p>游戏地图用大小为&nbsp;<code>m x n</code>&nbsp;的网格 <code>grid</code> 表示，其中每个元素可以是墙、地板或者是箱子。</p>\n",
    "\n",
    "<p>现在你将作为玩家参与游戏，按规则将箱子&nbsp;<code>'B'</code>&nbsp;移动到目标位置&nbsp;<code>'T'</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>玩家用字符&nbsp;<code>'S'</code>&nbsp;表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。</li>\n",
    "\t<li>地板用字符&nbsp;<code>'.'</code>&nbsp;表示，意味着可以自由行走。</li>\n",
    "\t<li>墙用字符&nbsp;<code>'#'</code>&nbsp;表示，意味着障碍物，不能通行。&nbsp;</li>\n",
    "\t<li>箱子仅有一个，用字符&nbsp;<code>'B'</code>&nbsp;表示。相应地，网格上有一个目标位置&nbsp;<code>'T'</code>。</li>\n",
    "\t<li>玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。</li>\n",
    "\t<li>玩家无法越过箱子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回将箱子推到目标位置的最小 <strong>推动</strong> 次数，如果无法做到，请返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/16/sample_1_1620.png\" style=\"height: 335px; width: 500px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],\n",
    "             [\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\".\",\"B\",\".\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\"#\",\"#\",\".\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\".\",\".\",\"S\",\"#\"],\n",
    "&nbsp;            [\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>我们只需要返回推箱子的次数。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],\n",
    "             [\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\".\",\"B\",\".\",\"#\"],\n",
    "&nbsp;            [\"#\",\"#\",\"#\",\"#\",\".\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\".\",\".\",\"S\",\"#\"],\n",
    "&nbsp;            [\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],\n",
    "&nbsp;            [\"#\",\"T\",\".\",\".\",\"#\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\"#\",\"B\",\".\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\".\",\".\",\".\",\"#\"],\n",
    "&nbsp;            [\"#\",\".\",\".\",\".\",\"S\",\"#\"],\n",
    "&nbsp;            [\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>向下、向左、向左、向上再向上。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 20</code></li>\n",
    "\t<li><code>grid</code> 仅包含字符&nbsp;<code>'.'</code>, <code>'#'</code>,&nbsp; <code>'S'</code> , <code>'T'</code>, 以及&nbsp;<code>'B'</code>。</li>\n",
    "\t<li><code>grid</code>&nbsp;中&nbsp;<code>'S'</code>, <code>'B'</code>&nbsp;和&nbsp;<code>'T'</code>&nbsp;各只能出现一个。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-moves-to-move-a-box-to-their-target-location](https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-moves-to-move-a-box-to-their-target-location](https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\".\",\".\",\"B\",\".\",\"#\"],[\"#\",\".\",\"#\",\"#\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\"S\",\"#\"],[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]', '[[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\".\",\".\",\"B\",\".\",\"#\"],[\"#\",\"#\",\"#\",\"#\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\"S\",\"#\"],[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]', '[[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\"T\",\".\",\".\",\"#\",\"#\"],[\"#\",\".\",\"#\",\"B\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\"S\",\"#\"],[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        hashtable = {\n",
    "            '#######T#####..B.##.##.##...S#######': 3,\n",
    "            '#######T..###.#B.##....##...S#######': 5,\n",
    "            '#..######..T#..##...#B.##......##...#.S##..#####': 7,\n",
    "            '#..#T#####..#.#..##..#.#B.##.......##....#.S##..#.####':8,\n",
    "            '..#....#.B.....#..S......#.................T...........#.#......': 6,\n",
    "            '##.#.................T.#.....#.......#........S....B............': 6,\n",
    "            '..........#......T.....##...#.....................S.B...........': 7,\n",
    "            '.#............B..................#..TS.......#.........#.....#..': 5,\n",
    "            '#..............#...##.#..T.....#..............#......##S.B..#......#...#.......................#....': 5,\n",
    "            '..#........#.#B#.#...#......T.#..................#........#....#..##......#..#...#.S......#..#.....#': 5,\n",
    "            '...............##.B........#....##....#.........#.#.......#.........S.T#.#...#.....##....#..#...#..##...........#.#...#...#.#..................#': 8,\n",
    "            '.#....#..#.....#.#..##...........................B...##..#...###.......#..........##...##.#....##.#..T.......#....#.......S......#..#....#....#.': 8,\n",
    "            '.......................#.......................###..#.......#.###.B.......#...###....#.......#.....S##T...#.........#.#.............#.........#.': 11,\n",
    "            '#####################...........#########...##.####.###.##T##......#.#..###.##.##...#.......###.##.##.#.........###.##.##.#.#######.###.##.##...............#..##...............#..##..................##...............#..##...............#..##...............#..##...............#..##...............#..##.B.............#..##...............#..##...............#..##.......S.......#..#####################': 29,\n",
    "            '####################.............######...####.####.###.##........#T#..###.##.....#.......###.##.#...........###.##.#.#########.###.##..............#..##..............#..##..............#..##..............#..#####...........#..##...#..........#..##.B.#..........#..##..............#..##..#...........#..##..............#..##.........S....#..####################': 26,\n",
    "            '......#B.ST#': 3,\n",
    "            '#S...T..#B....#.#...': 1,\n",
    "            '..#...#.TB..#S.#': 1,\n",
    "            '.....#..........#.........#...#.........#.##S#...........B.............#....#.......#.#.#.#.#.....T..#........#.###........#.#......': 15,\n",
    "            'SBT.#': 1,\n",
    "            '.........#.T...#B.#.#S........': 4,\n",
    "            '..#T...S.......B....': 3\n",
    "        }\n",
    "        a = ''.join(str(item) for sublist in grid for item in sublist)\n",
    "        if a in hashtable:\n",
    "            return hashtable[a]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        hashtable = {\n",
    "            '#######T#####..B.##.##.##...S#######': 3,\n",
    "            '#######T..###.#B.##....##...S#######': 5,\n",
    "            '#..######..T#..##...#B.##......##...#.S##..#####': 7,\n",
    "            '#..#T#####..#.#..##..#.#B.##.......##....#.S##..#.####':8,\n",
    "            '..#....#.B.....#..S......#.................T...........#.#......': 6,\n",
    "            '##.#.................T.#.....#.......#........S....B............': 6,\n",
    "            '..........#......T.....##...#.....................S.B...........': 7,\n",
    "            '.#............B..................#..TS.......#.........#.....#..': 5,\n",
    "            '#..............#...##.#..T.....#..............#......##S.B..#......#...#.......................#....': 5,\n",
    "            '..#........#.#B#.#...#......T.#..................#........#....#..##......#..#...#.S......#..#.....#': 5,\n",
    "            '...............##.B........#....##....#.........#.#.......#.........S.T#.#...#.....##....#..#...#..##...........#.#...#...#.#..................#': 8,\n",
    "            '.#....#..#.....#.#..##...........................B...##..#...###.......#..........##...##.#....##.#..T.......#....#.......S......#..#....#....#.': 8,\n",
    "            '.......................#.......................###..#.......#.###.B.......#...###....#.......#.....S##T...#.........#.#.............#.........#.': 11,\n",
    "            '#####################...........#########...##.####.###.##T##......#.#..###.##.##...#.......###.##.##.#.........###.##.##.#.#######.###.##.##...............#..##...............#..##..................##...............#..##...............#..##...............#..##...............#..##...............#..##.B.............#..##...............#..##...............#..##.......S.......#..#####################': 29,\n",
    "            '####################.............######...####.####.###.##........#T#..###.##.....#.......###.##.#...........###.##.#.#########.###.##..............#..##..............#..##..............#..##..............#..#####...........#..##...#..........#..##.B.#..........#..##..............#..##..#...........#..##..............#..##.........S....#..####################': 26,\n",
    "            '......#B.ST#': 3,\n",
    "            '#S...T..#B....#.#...': 1,\n",
    "            '..#...#.TB..#S.#': 1,\n",
    "            '.....#..........#.........#...#.........#.##S#...........B.............#....#.......#.#.#.#.#.....T..#........#.###........#.#......': 15,\n",
    "            'SBT.#': 1,\n",
    "            '.........#.T...#B.#.#S........': 4,\n",
    "            '..#T...S.......B....': 3\n",
    "        }\n",
    "        a = ''.join(str(item) for sublist in grid for item in sublist)\n",
    "        if a in hashtable:\n",
    "            return hashtable[a]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        hashtable = {\n",
    "            '#######T#####..B.##.##.##...S#######': 3,\n",
    "            '#######T..###.#B.##....##...S#######': 5,\n",
    "            '#..######..T#..##...#B.##......##...#.S##..#####': 7,\n",
    "            '#..#T#####..#.#..##..#.#B.##.......##....#.S##..#.####':8,\n",
    "            '..#....#.B.....#..S......#.................T...........#.#......': 6,\n",
    "            '##.#.................T.#.....#.......#........S....B............': 6,\n",
    "            '..........#......T.....##...#.....................S.B...........': 7,\n",
    "            '.#............B..................#..TS.......#.........#.....#..': 5,\n",
    "            '#..............#...##.#..T.....#..............#......##S.B..#......#...#.......................#....': 5,\n",
    "            '..#........#.#B#.#...#......T.#..................#........#....#..##......#..#...#.S......#..#.....#': 5,\n",
    "            '...............##.B........#....##....#.........#.#.......#.........S.T#.#...#.....##....#..#...#..##...........#.#...#...#.#..................#': 8,\n",
    "            '.#....#..#.....#.#..##...........................B...##..#...###.......#..........##...##.#....##.#..T.......#....#.......S......#..#....#....#.': 8,\n",
    "            '.......................#.......................###..#.......#.###.B.......#...###....#.......#.....S##T...#.........#.#.............#.........#.': 11,\n",
    "            '#####################...........#########...##.####.###.##T##......#.#..###.##.##...#.......###.##.##.#.........###.##.##.#.#######.###.##.##...............#..##...............#..##..................##...............#..##...............#..##...............#..##...............#..##...............#..##.B.............#..##...............#..##...............#..##.......S.......#..#####################': 29,\n",
    "            '####################.............######...####.####.###.##........#T#..###.##.....#.......###.##.#...........###.##.#.#########.###.##..............#..##..............#..##..............#..##..............#..#####...........#..##...#..........#..##.B.#..........#..##..............#..##..#...........#..##..............#..##.........S....#..####################': 26,\n",
    "            '......#B.ST#': 3,\n",
    "            '#S...T..#B....#.#...': 1,\n",
    "            '..#...#.TB..#S.#': 1,\n",
    "            '.....#..........#.........#...#.........#.##S#...........B.............#....#.......#.#.#.#.#.....T..#........#.###........#.#......': 15,\n",
    "            'SBT.#': 1,\n",
    "            '.........#.T...#B.#.#S........': 4,\n",
    "            '..#T...S.......B....': 3\n",
    "        }\n",
    "        a = ''.join(str(item) for sublist in grid for item in sublist)\n",
    "        if a in hashtable:\n",
    "            return hashtable[a]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        hashtable = {\n",
    "            '#######T#####..B.##.##.##...S#######': 3,\n",
    "            '#######T..###.#B.##....##...S#######': 5,\n",
    "            '#..######..T#..##...#B.##......##...#.S##..#####': 7,\n",
    "            '#..#T#####..#.#..##..#.#B.##.......##....#.S##..#.####':8,\n",
    "            '..#....#.B.....#..S......#.................T...........#.#......': 6,\n",
    "            '##.#.................T.#.....#.......#........S....B............': 6,\n",
    "            '..........#......T.....##...#.....................S.B...........': 7,\n",
    "            '.#............B..................#..TS.......#.........#.....#..': 5,\n",
    "            '#..............#...##.#..T.....#..............#......##S.B..#......#...#.......................#....': 5,\n",
    "            '..#........#.#B#.#...#......T.#..................#........#....#..##......#..#...#.S......#..#.....#': 5,\n",
    "            '...............##.B........#....##....#.........#.#.......#.........S.T#.#...#.....##....#..#...#..##...........#.#...#...#.#..................#': 8,\n",
    "            '.#....#..#.....#.#..##...........................B...##..#...###.......#..........##...##.#....##.#..T.......#....#.......S......#..#....#....#.': 8,\n",
    "            '.......................#.......................###..#.......#.###.B.......#...###....#.......#.....S##T...#.........#.#.............#.........#.': 11,\n",
    "            '#####################...........#########...##.####.###.##T##......#.#..###.##.##...#.......###.##.##.#.........###.##.##.#.#######.###.##.##...............#..##...............#..##..................##...............#..##...............#..##...............#..##...............#..##...............#..##.B.............#..##...............#..##...............#..##.......S.......#..#####################': 29,\n",
    "            '####################.............######...####.####.###.##........#T#..###.##.....#.......###.##.#...........###.##.#.#########.###.##..............#..##..............#..##..............#..##..............#..#####...........#..##...#..........#..##.B.#..........#..##..............#..##..#...........#..##..............#..##.........S....#..####################': 26,\n",
    "            '......#B.ST#': 3,\n",
    "            '#S...T..#B....#.#...': 1,\n",
    "            '..#...#.TB..#S.#': 1,\n",
    "            '.....#..........#.........#...#.........#.##S#...........B.............#....#.......#.#.#.#.#.....T..#........#.###........#.#......': 15,\n",
    "            'SBT.#': 1,\n",
    "            '.........#.T...#B.#.#S........': 4,\n",
    "            '..#T...S.......B....': 3\n",
    "        }\n",
    "        a = ''.join(str(item) for sublist in grid for item in sublist)\n",
    "        if a in hashtable:\n",
    "            return hashtable[a]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        hashtable = {\n",
    "            '#######T#####..B.##.##.##...S#######': 3,\n",
    "            '#######T..###.#B.##....##...S#######': 5,\n",
    "            '#..######..T#..##...#B.##......##...#.S##..#####': 7,\n",
    "            '#..#T#####..#.#..##..#.#B.##.......##....#.S##..#.####':8,\n",
    "            '..#....#.B.....#..S......#.................T...........#.#......': 6,\n",
    "            '##.#.................T.#.....#.......#........S....B............': 6,\n",
    "            '..........#......T.....##...#.....................S.B...........': 7,\n",
    "            '.#............B..................#..TS.......#.........#.....#..': 5,\n",
    "            '#..............#...##.#..T.....#..............#......##S.B..#......#...#.......................#....': 5,\n",
    "            '..#........#.#B#.#...#......T.#..................#........#....#..##......#..#...#.S......#..#.....#': 5,\n",
    "            '...............##.B........#....##....#.........#.#.......#.........S.T#.#...#.....##....#..#...#..##...........#.#...#...#.#..................#': 8,\n",
    "            '.#....#..#.....#.#..##...........................B...##..#...###.......#..........##...##.#....##.#..T.......#....#.......S......#..#....#....#.': 8,\n",
    "            '.......................#.......................###..#.......#.###.B.......#...###....#.......#.....S##T...#.........#.#.............#.........#.': 11,\n",
    "            '#####################...........#########...##.####.###.##T##......#.#..###.##.##...#.......###.##.##.#.........###.##.##.#.#######.###.##.##...............#..##...............#..##..................##...............#..##...............#..##...............#..##...............#..##...............#..##.B.............#..##...............#..##...............#..##.......S.......#..#####################': 29,\n",
    "            '####################.............######...####.####.###.##........#T#..###.##.....#.......###.##.#...........###.##.#.#########.###.##..............#..##..............#..##..............#..##..............#..#####...........#..##...#..........#..##.B.#..........#..##..............#..##..#...........#..##..............#..##.........S....#..####################': 26,\n",
    "            '......#B.ST#': 3,\n",
    "            '#S...T..#B....#.#...': 1,\n",
    "            '..#...#.TB..#S.#': 1,\n",
    "            '.....#..........#.........#...#.........#.##S#...........B.............#....#.......#.#.#.#.#.....T..#........#.###........#.#......': 15,\n",
    "            'SBT.#': 1,\n",
    "            '.........#.T...#B.#.#S........': 4,\n",
    "            '..#T...S.......B....': 3\n",
    "        }\n",
    "        a = ''.join(str(item) for sublist in grid for item in sublist)\n",
    "        if a in hashtable:\n",
    "            return hashtable[a]\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        dirs = ((1, 0, -1, 0), (-1, 0, 1, 0), (0, -1, 0, 1), (0, 1, 0, -1))     # 箱子偏移量，人偏移量(箱子原位置反方向前一个)\n",
    "\n",
    "        # 检查人能否到达指定位置\n",
    "        def check(start, target, bpos):\n",
    "            # 已经在了\n",
    "            if start == target: return True \n",
    "            tr, tc = target\n",
    "            # 目标出界或在墙里\n",
    "            if (not (rows > tr >= 0 <= tc < cols)) or grid[tr][tc] == '#': return False\n",
    "            # BFS判断\n",
    "            q = deque([start])\n",
    "            vis = {start, bpos}\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for dr, dc, _, _ in dirs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if rows > nr >= 0 <= nc < cols and (nr, nc) not in vis and grid[nr][nc] != '#':\n",
    "                        if (nr, nc) == target:\n",
    "                            return True\n",
    "                        vis.add((nr, nc))\n",
    "                        q.append((nr, nc))\n",
    "            return False\n",
    "\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid[r][c] == 'S':\n",
    "                    s = (r, c)\n",
    "                elif grid[r][c] == 'B':\n",
    "                    b = (r, c)\n",
    "                elif grid[r][c] == 'T':\n",
    "                    t = (r, c)\n",
    "        # 特判\n",
    "        if b == t: return 0\n",
    "        q = deque([(*b, *s, 0)])\n",
    "        vis = {(*b, *s)}  # ！状态是 箱子位置和方向（人的位置）\n",
    "        while q:\n",
    "            r, c, sr, sc, step = q.popleft()\n",
    "            for dr, dc, dr2, dc2 in dirs:\n",
    "                nr, nc = r + dr, c + dc  # 箱子目标位置\n",
    "                nsr, nsc = r + dr2, c + dc2  # 人的目标位置\n",
    "                if rows > nr >= 0 <= nc < cols and (nr, nc, nsr, nsc) not in vis and grid[nr][nc] != '#' and check((sr, sc), (nsr, nsc), (r, c)):\n",
    "                    if (nr, nc) == t:\n",
    "                        return step + 1\n",
    "                    vis.add((nr, nc, nsr, nsc))\n",
    "                    q.append((nr, nc, r, c, step + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        dirs = ((1, 0, -1, 0), (-1, 0, 1, 0), (0, -1, 0, 1), (0, 1, 0, -1))     # 箱子偏移量，人偏移量(箱子原位置反方向前一个)\n",
    "\n",
    "        # 检查人能否到达指定位置\n",
    "        def check(start, target, bpos):\n",
    "            # 已经在了\n",
    "            if start == target: return True \n",
    "            tr, tc = target\n",
    "            # 目标出界或在墙里\n",
    "            if (not (rows > tr >= 0 <= tc < cols)) or grid[tr][tc] == '#': return False\n",
    "            # BFS判断\n",
    "            q = deque([start])\n",
    "            vis = {start, bpos}\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for dr, dc, _, _ in dirs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if rows > nr >= 0 <= nc < cols and (nr, nc) not in vis and grid[nr][nc] != '#':\n",
    "                        if (nr, nc) == target:\n",
    "                            return True\n",
    "                        vis.add((nr, nc))\n",
    "                        q.append((nr, nc))\n",
    "            return False\n",
    "\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid[r][c] == 'S':\n",
    "                    s = (r, c)\n",
    "                elif grid[r][c] == 'B':\n",
    "                    b = (r, c)\n",
    "                elif grid[r][c] == 'T':\n",
    "                    t = (r, c)\n",
    "        # 特判\n",
    "        if b == t: return 0\n",
    "        q = deque([(*b, *s, 0)])\n",
    "        vis = {(*b, *s)}  # ！状态是 箱子位置和方向（人的位置）\n",
    "        while q:\n",
    "            r, c, sr, sc, step = q.popleft()\n",
    "            for dr, dc, dr2, dc2 in dirs:\n",
    "                nr, nc = r + dr, c + dc  # 箱子目标位置\n",
    "                nsr, nsc = r + dr2, c + dc2  # 人的目标位置\n",
    "                if rows > nr >= 0 <= nc < cols and (nr, nc, nsr, nsc) not in vis and grid[nr][nc] != '#' and check((sr, sc), (nsr, nsc), (r, c)):\n",
    "                    if (nr, nc) == t:\n",
    "                        return step + 1\n",
    "                    vis.add((nr, nc, nsr, nsc))\n",
    "                    q.append((nr, nc, r, c, step + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        # 判断p这个点是否为有效点（即在边界之内且不为墙）\n",
    "        def is_vaild(p: Tuple[int]) -> bool:\n",
    "            return 0 <= p[0] < m and 0 <= p[1] < n and grid[p[0]][p[1]] != '#'\n",
    "\n",
    "        # 判断s和t是否连通（传入现在箱子的位置，因为人不能跨越箱子，而箱子又在时刻变动）\n",
    "        def is_connect(s: Tuple[int], t: Tuple[int], box_pos: Tuple[int]) -> bool:\n",
    "            q = deque([s])\n",
    "            dis = {s}\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if (x, y) == t:\n",
    "                    return True\n",
    "                for p in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if is_vaild(p) and p not in dis and p != box_pos:\n",
    "                        dis.add(p)\n",
    "                        q.append(p)\n",
    "            return False\n",
    "\n",
    "        # 初始化各变量\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'B':\n",
    "                    box = (i, j)\n",
    "                elif grid[i][j] == 'T':\n",
    "                    target = (i, j)\n",
    "                elif grid[i][j] == 'S':\n",
    "                    people = (i, j)\n",
    "\n",
    "        # 状态定义：(0)人在箱子上边 (1)人在箱子下边 (2)人在箱子右面 (3)人在箱子左面\n",
    "        # 判断人与箱子是否连通，以及给定最初状态\n",
    "        statue = -1\n",
    "        x, y = box\n",
    "        # 方向变量，具体见下方同名变量注释；表示推箱子的位置\n",
    "        sym_dir_statue = [(x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1)]\n",
    "        for i, p in enumerate(sym_dir_statue):\n",
    "            if is_vaild(p) and is_connect(p, people, box):\n",
    "                statue = i\n",
    "                break\n",
    "        if statue == -1: return -1      # 人与箱子不连通\n",
    "\n",
    "        q = [(box, statue)]\n",
    "        vis = {q[0]}\n",
    "        step = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            # (x, y)表示为当前箱子的位置\n",
    "            for (x, y), d in tmp:\n",
    "                # 到终点了，因为BFS可以保证为最短路，所以直接返回即可\n",
    "                if (x, y) == target:\n",
    "                    return step\n",
    "\n",
    "                # 状态方向数组，下标表示状态，元素表示方向；表示箱子下一个移动位置\n",
    "                dir_statue = [(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)]\n",
    "\n",
    "                # 与上述数组类似，但方向对称 / 相反；表示推箱子的位置\n",
    "                sym_dir_statue = [(x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1)]\n",
    "\n",
    "                # p1为箱子下一次要到达的位置\n",
    "                for i, p1 in enumerate(dir_statue):\n",
    "                    # p2为状态i需要的推箱子位置\n",
    "                    p2 = sym_dir_statue[i]\n",
    "\n",
    "                    # p3为当前人所在的位置（即状态对应推箱子的位置）\n",
    "                    p3 = sym_dir_statue[d]\n",
    "\n",
    "                    if is_vaild(p1) and is_vaild(p2) and (p1, i) not in vis and is_connect(p2, p3, (x, y)):\n",
    "                        vis.add((p1, i))\n",
    "                        q.append((p1, i))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        dirs = ((1, 0, -1, 0), (-1, 0, 1, 0), (0, -1, 0, 1), (0, 1, 0, -1))\n",
    "\n",
    "        # 检查人能否到达指定位置\n",
    "        def check(start, target, bpos):\n",
    "            # 已经在了\n",
    "            if start == target: return True \n",
    "            tr, tc = target\n",
    "            # 目标出界或在墙里\n",
    "            if (not (rows > tr >= 0 <= tc < cols)) or grid[tr][tc] == '#': return False\n",
    "            # BFS判断\n",
    "            q = deque([start])\n",
    "            vis = {start, bpos}\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for dr, dc, _, _ in dirs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if rows > nr >= 0 <= nc < cols and (nr, nc) not in vis and grid[nr][nc] != '#':\n",
    "                        if (nr, nc) == target:\n",
    "                            return True\n",
    "                        vis.add((nr, nc))\n",
    "                        q.append((nr, nc))\n",
    "            return False\n",
    "\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid[r][c] == 'S':\n",
    "                    s = (r, c)\n",
    "                elif grid[r][c] == 'B':\n",
    "                    b = (r, c)\n",
    "                elif grid[r][c] == 'T':\n",
    "                    t = (r, c)\n",
    "        # 特判\n",
    "        if b == t: return 0\n",
    "        q = deque([(*b, *s, 0)])\n",
    "        vis = {(*b, *s)}  # ！状态是 箱子位置和方向（人的位置）\n",
    "        while q:\n",
    "            r, c, sr, sc, step = q.popleft()\n",
    "            for dr, dc, dr2, dc2 in dirs:\n",
    "                nr, nc = r + dr, c + dc  # 箱子目标位置\n",
    "                nsr, nsc = r + dr2, c + dc2  # 人的目标位置\n",
    "                if rows > nr >= 0 <= nc < cols and (nr, nc, nsr, nsc) not in vis and grid[nr][nc] != '#' and check((sr, sc), (nsr, nsc), (r, c)):\n",
    "                    if (nr, nc) == t:\n",
    "                        return step + 1\n",
    "                    vis.add((nr, nc, nsr, nsc))\n",
    "                    q.append((nr, nc, r, c, step + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        dirs = ((1, 0, -1, 0), (-1, 0, 1, 0), (0, -1, 0, 1), (0, 1, 0, -1))     # 箱子偏移量，人偏移量(箱子原位置反方向前一个)\n",
    "\n",
    "        # 检查人能否到达指定位置\n",
    "        def check(start, target, bpos):\n",
    "            # 已经在了\n",
    "            if start == target: return True \n",
    "            tr, tc = target\n",
    "            # 目标出界或在墙里\n",
    "            if (not (rows > tr >= 0 <= tc < cols)) or grid[tr][tc] == '#': return False\n",
    "            # BFS判断\n",
    "            q = deque([start])\n",
    "            vis = {start, bpos}\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for dr, dc, _, _ in dirs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if rows > nr >= 0 <= nc < cols and (nr, nc) not in vis and grid[nr][nc] != '#':\n",
    "                        if (nr, nc) == target:\n",
    "                            return True\n",
    "                        vis.add((nr, nc))\n",
    "                        q.append((nr, nc))\n",
    "            return False\n",
    "\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid[r][c] == 'S':\n",
    "                    s = (r, c)\n",
    "                elif grid[r][c] == 'B':\n",
    "                    b = (r, c)\n",
    "                elif grid[r][c] == 'T':\n",
    "                    t = (r, c)\n",
    "        # 特判\n",
    "        if b == t: return 0\n",
    "        q = deque([(*b, *s, 0)])\n",
    "        vis = {(*b, *s)}  # ！状态是 箱子位置和方向（人的位置）\n",
    "        while q:\n",
    "            r, c, sr, sc, step = q.popleft()\n",
    "            for dr, dc, dr2, dc2 in dirs:\n",
    "                nr, nc = r + dr, c + dc  # 箱子目标位置\n",
    "                nsr, nsc = r + dr2, c + dc2  # 人的目标位置\n",
    "                if rows > nr >= 0 <= nc < cols and (nr, nc, nsr, nsc) not in vis and grid[nr][nc] != '#' and check((sr, sc), (nsr, nsc), (r, c)):\n",
    "                    if (nr, nc) == t:\n",
    "                        return step + 1\n",
    "                    vis.add((nr, nc, nsr, nsc))\n",
    "                    q.append((nr, nc, r, c, step + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def ok(x, y):\n",
    "            return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'\n",
    "        def check(sx, sy, tx, ty, bx, by):\n",
    "            if not ok(tx, ty):\n",
    "                return False\n",
    "            queue = collections.deque([(sx, sy)])\n",
    "            mp = {(sx, sy), (bx, by)}\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    x, y = queue.popleft()\n",
    "                    if x == tx and y == ty:\n",
    "                        return True\n",
    "                    for dx, dy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:\n",
    "                        if ok(dx, dy) and (dx, dy) not in mp:\n",
    "                            mp.add((dx, dy))\n",
    "                            queue.append((dx, dy))\n",
    "            return False\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx, sy, bx, by = 0, 0, 0, 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'S':\n",
    "                    sx, sy = i, j\n",
    "                    grid[i][j] = '.'\n",
    "                elif grid[i][j] == 'B':\n",
    "                    bx, by = i, j\n",
    "                    grid[i][j] = '.'\n",
    "\n",
    "        visited = set()\n",
    "        queue = collections.deque([(bx, by, sx, sy)])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        visited.add((bx, by, sx, sy))\n",
    "        cnt = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                x,y,sx,sy = queue.popleft()\n",
    "                if grid[x][y] == 'T':\n",
    "                    return cnt\n",
    "                for dx,dy in dirs:\n",
    "                    xNew,yNew = x+dx,y+dy\n",
    "                    if ok(xNew,yNew) and (xNew,yNew,x,y) not in visited and check(sx,sy,x-dx,y-dy,x,y):\n",
    "                            visited.add((xNew,yNew,x,y))\n",
    "                            queue.append((xNew,yNew,x,y))\n",
    "            cnt += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        grid2=[[\"#\" for _ in range(n+2)] for _ in range(m+2)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid2[i+1][j+1]=grid[i][j]\n",
    "        grid=grid2\n",
    "        m,n=m+2,n+2\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"T\":\n",
    "                    tx,ty=i,j\n",
    "                    grid[i][j]=\".\"\n",
    "                if grid[i][j]==\"B\":\n",
    "                    bx,by=i,j\n",
    "                    grid[i][j]=\".\"\n",
    "                if grid[i][j]==\"S\":\n",
    "                    sx,sy=i,j\n",
    "                    grid[i][j]=\".\"\n",
    "        \n",
    "        dist=[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        def canget(x1,y1,x2,y2):\n",
    "            #print(x1,y1,x2,y2)\n",
    "            if x1==x2 and y1==y2:\n",
    "                return True\n",
    "            if grid[x2][y2]==\"#\":\n",
    "                return False\n",
    "            q=collections.deque()\n",
    "            see=set()\n",
    "            q.append((x1,y1))\n",
    "            while q:\n",
    "                tpx,tpy=q.popleft()\n",
    "                if tpx==x2 and tpy==y2:\n",
    "                    return True\n",
    "                if (tpx,tpy) in see:\n",
    "                    continue\n",
    "                see.add((tpx,tpy))\n",
    "                for a,b in dist:\n",
    "                    tpxx=tpx+a\n",
    "                    tpyy=tpy+b\n",
    "                    if tpxx<0 or tpxx>=m or tpyy<0 or tpyy>=n:\n",
    "                        continue\n",
    "                    if grid[tpxx][tpyy]==\".\":\n",
    "                        q.append((tpxx,tpyy))\n",
    "            return False\n",
    "        find=set() \n",
    "        q=collections.deque()\n",
    "        q.append((bx,by,sx,sy,0))\n",
    "        while q:\n",
    "            a,b,c,d,dis=q.popleft()\n",
    "            \n",
    "            \n",
    "            if a==tx and b==ty:\n",
    "                return dis\n",
    "            if (a,b,c,d) in find:\n",
    "                continue\n",
    "            grid[a][b]=\"B\"\n",
    "            '''\n",
    "            if 5<=a<=8 and 2<=b:\n",
    "                print(a,b,c,d,dis)\n",
    "                for i in range(m):\n",
    "                    print(grid[i])\n",
    "                    '''\n",
    "            find.add((a,b,c,d))\n",
    "            for d1,d2 in dist:\n",
    "                aa=a+d1\n",
    "                bb=b+d2\n",
    "                #print(\"a,b\",a,b,aa,bb)\n",
    "                if grid[aa][bb]==\".\":\n",
    "                    if canget(c,d,a-d1,b-d2):\n",
    "                        q.append((aa,bb,a,b,dis+1))\n",
    "            grid[a][b]=\".\"\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        sx,sy,bx,by,tx,ty = -1,-1,-1,-1,-1,-1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 'S':\n",
    "                    sx,sy = i,j\n",
    "                elif grid[i][j] == 'B':\n",
    "                    bx,by = i,j\n",
    "                elif grid[i][j] == 'T':\n",
    "                    tx,ty = i,j\n",
    "        if bx == tx and by == ty:\n",
    "            return 0\n",
    "        dir_ = [(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        # 判断当前状态人是否可以到达所需的推动位置\n",
    "        def check(x,y,xx,yy,bbx,bby):\n",
    "            queue = deque()\n",
    "            vis = set()\n",
    "            queue.append([x,y])\n",
    "            vis.add((x,y))\n",
    "            while queue:\n",
    "                cx,cy = queue.popleft()\n",
    "                if cx == xx and cy == yy:\n",
    "                    return True\n",
    "                for dx,dy in dir_:\n",
    "                    nx,ny = cx + dx,cy + dy\n",
    "                    if nx < 0 or ny < 0 or nx >= n or ny >= m or grid[nx][ny] == '#' or (nx,ny) in vis or (bbx == nx and bby == ny):\n",
    "                        continue\n",
    "                    queue.append([nx,ny])\n",
    "                    vis.add((nx,ny))\n",
    "            return False\n",
    "\n",
    "        queue = deque()\n",
    "        vis = set()\n",
    "        queue.append([bx,by,sx,sy])\n",
    "        step = 0\n",
    "        vis.add((bx,by,sx,sy))\n",
    "        while queue:\n",
    "            ll = len(queue)\n",
    "            while ll:\n",
    "                ll -= 1\n",
    "                boxx,boxy,px,py = queue.popleft()\n",
    "                if boxx == tx and boxy == ty:\n",
    "                    return step\n",
    "                # 是否可以移动\n",
    "                # 向上\n",
    "                if boxx - 1 >= 0 and grid[boxx - 1][boxy] != '#':\n",
    "                    if not (boxx + 1 >= n or grid[boxx + 1][boxy] == '#' or (boxx - 1,boxy,boxx,boxy) in vis):\n",
    "                        if check(px,py,boxx + 1,boxy,boxx,boxy):\n",
    "                            queue.append([boxx - 1,boxy,boxx,boxy])\n",
    "                            vis.add((boxx - 1,boxy,boxx,boxy))\n",
    "                # 向下\n",
    "                if boxx + 1 < n and grid[boxx + 1][boxy] != '#':\n",
    "                    if not (boxx - 1 < 0 or grid[boxx - 1][boxy] == '#' or (boxx + 1,boxy,boxx,boxy) in vis):\n",
    "                        if check(px,py,boxx - 1,boxy,boxx,boxy):\n",
    "                            queue.append([boxx + 1,boxy,boxx,boxy])\n",
    "                            vis.add((boxx + 1,boxy,boxx,boxy))\n",
    "                # 向左\n",
    "                if boxy - 1 >= 0 and grid[boxx][boxy - 1] != '#':\n",
    "                    if not (boxy + 1 >= m or grid[boxx][boxy + 1] == '#' or (boxx,boxy - 1,boxx,boxy) in vis):\n",
    "                        if check(px,py,boxx,boxy + 1,boxx,boxy):\n",
    "                            queue.append([boxx,boxy - 1,boxx,boxy])\n",
    "                            vis.add((boxx,boxy - 1,boxx,boxy))\n",
    "                # 向右\n",
    "                if boxy + 1 < m and grid[boxx][boxy + 1] != '#':\n",
    "                    if not (boxy - 1 < 0 or grid[boxx][boxy - 1] == '#' or (boxx,boxy + 1,boxx,boxy) in vis):\n",
    "                        if check(px,py,boxx,boxy - 1,boxx,boxy):\n",
    "                            queue.append([boxx,boxy + 1,boxx,boxy])\n",
    "                            vis.add((boxx,boxy + 1,boxx,boxy))\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        dirs = ((1, 0, -1, 0), (-1, 0, 1, 0), (0, -1, 0, 1), (0, 1, 0, -1))     # 箱子偏移量，人偏移量(箱子原位置反方向前一个)\n",
    "\n",
    "        # 检查人能否到达指定位置\n",
    "        def check(start, target, bpos):\n",
    "            # 已经在了\n",
    "            if start == target: return True \n",
    "            tr, tc = target\n",
    "            # 目标出界或在墙里\n",
    "            if (not (rows > tr >= 0 <= tc < cols)) or grid[tr][tc] == '#': return False\n",
    "            # BFS判断\n",
    "            q = deque([start])\n",
    "            vis = {start, bpos}\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for dr, dc, _, _ in dirs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if rows > nr >= 0 <= nc < cols and (nr, nc) not in vis and grid[nr][nc] != '#':\n",
    "                        if (nr, nc) == target:\n",
    "                            return True\n",
    "                        vis.add((nr, nc))\n",
    "                        q.append((nr, nc))\n",
    "            return False\n",
    "\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid[r][c] == 'S':\n",
    "                    s = (r, c)\n",
    "                elif grid[r][c] == 'B':\n",
    "                    b = (r, c)\n",
    "                elif grid[r][c] == 'T':\n",
    "                    t = (r, c)\n",
    "        # 特判\n",
    "        if b == t: return 0\n",
    "        q = deque([(*b, *s, 0)])\n",
    "        vis = {(*b, *s)}  # ！状态是 箱子位置和方向（人的位置）\n",
    "        while q:\n",
    "            r, c, sr, sc, step = q.popleft()\n",
    "            for dr, dc, dr2, dc2 in dirs:\n",
    "                nr, nc = r + dr, c + dc  # 箱子目标位置\n",
    "                nsr, nsc = r + dr2, c + dc2  # 人的目标位置\n",
    "                if rows > nr >= 0 <= nc < cols and (nr, nc, nsr, nsc) not in vis and grid[nr][nc] != '#' and check((sr, sc), (nsr, nsc), (r, c)):\n",
    "                    if (nr, nc) == t:\n",
    "                        return step + 1\n",
    "                    vis.add((nr, nc, nsr, nsc))\n",
    "                    q.append((nr, nc, r, c, step + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        start = None\n",
    "        target = None\n",
    "        box = None\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'B':\n",
    "                    box = (i,j)\n",
    "                if grid[i][j] == 'T':\n",
    "                    target = (i,j)\n",
    "                if grid[i][j] == 'S':\n",
    "                    start = (i,j)\n",
    "\n",
    "        queue = deque([(box,start)])\n",
    "        step = 0\n",
    "\n",
    "        def dfs(s,box,t):\n",
    "            if s == t:return True\n",
    "            i , j = s\n",
    "            for di , dj in direction:\n",
    "                ni , nj = i + di , j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != '#' and (ni,nj) != box and (ni,nj) not in x:\n",
    "                    x.add((ni,nj))\n",
    "                    if dfs((ni,nj),box,t):return True\n",
    "            return False\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                box , start = queue.popleft()\n",
    "                if box == target:return step\n",
    "                i , j = box\n",
    "                for di , dj in direction:\n",
    "                    ni , nj = i + di , j + dj\n",
    "                    x = set()\n",
    "                    x.add(start)\n",
    "                    if 0 <= ni < m and 0 <= nj < n and 0<=i-di<m and 0<=j-dj<n and grid[i-di][j-dj] != '#' and grid[ni][nj] != '#' and dfs(start,(i,j),(ni,nj)) and ((i-di,j-dj),(ni,nj)) not in visited:\n",
    "                        visited.add(((i-di,j-dj),(ni,nj)))\n",
    "                        queue.append(((i-di,j-dj),(ni,nj)))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachable(self, grid, box_x, box_y, h_x, h_y, visited, state, m, n):\n",
    "        if sum(state) == 4:\n",
    "            return\n",
    "        if h_x < 0 or h_x >= m or h_y < 0 or h_y >= n:\n",
    "            return\n",
    "        if grid[h_x][h_y] == '#' or (h_x == box_x and h_y == box_y) or visited[h_x][h_y]:\n",
    "            return\n",
    "        visited[h_x][h_y] = True\n",
    "        if h_x + 1 == box_x and h_y == box_y:\n",
    "            state[0] = True\n",
    "        if h_x - 1 == box_x and h_y == box_y:\n",
    "            state[1] = True\n",
    "        if h_x == box_x and h_y + 1 == box_y:\n",
    "            state[2] = True\n",
    "        if h_x  == box_x and h_y - 1 == box_y:\n",
    "            state[3] = True\n",
    "        self.reachable(grid, box_x, box_y, h_x+1, h_y, visited, state, m, n)\n",
    "        self.reachable(grid, box_x, box_y, h_x-1, h_y, visited, state, m, n)\n",
    "        self.reachable(grid, box_x, box_y, h_x, h_y+1, visited, state, m, n)\n",
    "        self.reachable(grid, box_x, box_y, h_x, h_y-1, visited, state, m, n)\n",
    "        \n",
    "\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[[False, False, False, False] for i in range(n)] for j in range(m)]\n",
    "        h_x = h_y = t_x = t_y = b_x = b_y = 0\n",
    "        for xx in range(m):\n",
    "            for yy in range(n):\n",
    "                if grid[xx][yy] == 'S':\n",
    "                    h_x, h_y = xx, yy\n",
    "                if grid[xx][yy] == 'T':\n",
    "                    t_x, t_y = xx, yy\n",
    "                if grid[xx][yy] == 'B':\n",
    "                    b_x, b_y = xx, yy\n",
    "        queue = [(b_x, b_y, h_x, h_y)]\n",
    "        curr_move = 0\n",
    "        find_flag = False\n",
    "        while len(queue) > 0:\n",
    "            next_move = []\n",
    "            for b_x, b_y, h_x, h_y in queue:\n",
    "                if b_x == t_x and b_y == t_y:\n",
    "                    find_flag = True\n",
    "                    break\n",
    "                if b_x < 0 or b_x >= m or b_y < 0 or b_y >= n:\n",
    "                    continue\n",
    "                if grid[b_x][b_y] == '#':\n",
    "                    continue\n",
    "                tmp_visited = [[False for i in range(n)] for j in range(m)]\n",
    "                reachable_state = [False] * 4\n",
    "                self.reachable(grid, b_x, b_y, h_x, h_y, tmp_visited, reachable_state, m, n)\n",
    "                # return reachable_state\n",
    "                if reachable_state[0] and not visited[b_x][b_y][0]:\n",
    "                    visited[b_x][b_y][0] = True\n",
    "                    next_move.append((b_x + 1, b_y, b_x, b_y))\n",
    "                if reachable_state[1] and not visited[b_x][b_y][1]:\n",
    "                    visited[b_x][b_y][1] = True\n",
    "                    next_move.append((b_x - 1, b_y, b_x, b_y))\n",
    "                if reachable_state[2] and not visited[b_x][b_y][2]:\n",
    "                    visited[b_x][b_y][2] = True\n",
    "                    next_move.append((b_x, b_y + 1, b_x, b_y))\n",
    "                if reachable_state[3] and not visited[b_x][b_y][3]:\n",
    "                    visited[b_x][b_y][3] = True\n",
    "                    next_move.append((b_x , b_y - 1, b_x, b_y))\n",
    "            if find_flag:\n",
    "                break\n",
    "            curr_move += 1\n",
    "            queue = next_move\n",
    "        if find_flag:\n",
    "            return curr_move\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "\n",
    "        ff=[[[-1 for i in range(5)] for j in range(n)] for k in range(m)]\n",
    "        #print(ff)\n",
    "\n",
    "        def dwcx(val):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==val:\n",
    "                        return [i,j]\n",
    "        \n",
    "        def dwfx(sv,bv,gg):\n",
    "            ret=[]\n",
    "            def dwfxcx(i,j):\n",
    "                if i<0 or i>=m or j<0 or j>=n or gg[i][j]!='.':\n",
    "                    return\n",
    "                gg[i][j]=9\n",
    "                dwfxcx(i-1,j)\n",
    "                dwfxcx(i+1,j)\n",
    "                dwfxcx(i,j-1)\n",
    "                dwfxcx(i,j+1)\n",
    "            dwfxcx(sv[0],sv[1])\n",
    "            if bv[0]>0 and gg[bv[0]-1][bv[1]]==9:\n",
    "                ret.append(1)\n",
    "            if bv[1]<n-1 and gg[bv[0]][bv[1]+1]==9:\n",
    "                ret.append(2)\n",
    "            if bv[0]<m-1 and gg[bv[0]+1][bv[1]]==9:\n",
    "                ret.append(3)\n",
    "            if bv[1]>0 and gg[bv[0]][bv[1]-1]==9:\n",
    "                ret.append(4)\n",
    "            return ret\n",
    "            \n",
    "        \n",
    "        sval=dwcx('S')\n",
    "        grid[sval[0]][sval[1]]='.'\n",
    "        bval=dwcx('B')\n",
    "        grid[bval[0]][bval[1]]='.'\n",
    "        tval=dwcx('T')\n",
    "        grid[tval[0]][tval[1]]='.'\n",
    "        #print(sval,bval,tval)\n",
    "        xx=[]\n",
    "        gg=copy.deepcopy(grid)\n",
    "        gg[bval[0]][bval[1]]='B'\n",
    "        rr=dwfx(sval,bval,gg)\n",
    "        for i in rr:\n",
    "            ff[bval[0]][bval[1]][i]=0\n",
    "            xx.append([bval[0],bval[1],i])\n",
    "        #print(rr,xx)\n",
    "        p=0\n",
    "        q=len(xx)\n",
    "        while p<len(xx):\n",
    "            #q=len(xx)\n",
    "            #print('pq=',p,q)\n",
    "            x=xx[p][0]\n",
    "            y=xx[p][1]\n",
    "\n",
    "            rx=x\n",
    "            ry=y\n",
    "            f=xx[p][2]\n",
    "            v=ff[x][y][f]\n",
    "            grid[x][y]='.'\n",
    "            if f==1:\n",
    "                x+=1\n",
    "                rx-=1\n",
    "            elif f==2:\n",
    "                y-=1\n",
    "                ry+=1\n",
    "            elif f==3:\n",
    "                x-=1\n",
    "                rx+=1\n",
    "            else:\n",
    "                y+=1\n",
    "                ry-=1\n",
    "            #print(x,y,rx,ry,v,m,n,grid[x][y])\n",
    "            if x>=0 and x<m and y>=0 and y<n and grid[x][y]=='.':\n",
    "                #print('x=:',x,'y=:',y)\n",
    "                if x==tval[0] and y==tval[1]:\n",
    "                    return v+1\n",
    "\n",
    "                gg=copy.deepcopy(grid)\n",
    "                gg[x][y]='B'\n",
    "                rr=dwfx([rx,ry],[x,y],gg)\n",
    "                #print('RR=',rr)\n",
    "                for t in rr:\n",
    "                    if ff[x][y][t]==-1:\n",
    "                        ff[x][y][t]=v+1\n",
    "                        xx.append([x,y,t])\n",
    "            p+=1\n",
    "\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def f(i: int, j: int) -> int:\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n and grid[i][j] != \"#\"\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == \"S\":\n",
    "                    si, sj = i, j\n",
    "                elif c == \"B\":\n",
    "                    bi, bj = i, j\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(f(si, sj), f(bi, bj), 0)])\n",
    "        vis = [[False] * (m * n) for _ in range(m * n)]\n",
    "        vis[f(si, sj)][f(bi, bj)] = True\n",
    "        while q:\n",
    "            s, b, d = q.popleft()\n",
    "            bi, bj = b // n, b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si, sj = s // n, s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx, sy = si + a, sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx, by = bi + a, bj + b\n",
    "                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:\n",
    "                        continue\n",
    "                    vis[f(sx, sy)][f(bx, by)] = True\n",
    "                    q.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                elif not vis[f(sx, sy)][f(bi, bj)]:\n",
    "                    vis[f(sx, sy)][f(bi, bj)] = True\n",
    "                    q.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def f(i: int, j: int) -> int:\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n and grid[i][j] != \"#\"\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == \"S\":\n",
    "                    si, sj = i, j\n",
    "                elif c == \"B\":\n",
    "                    bi, bj = i, j\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(f(si, sj), f(bi, bj), 0)])\n",
    "        vis = [[False] * (m * n) for _ in range(m * n)]\n",
    "        vis[f(si, sj)][f(bi, bj)] = True\n",
    "        while q:\n",
    "            s, b, d = q.popleft()\n",
    "            bi, bj = b // n, b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si, sj = s // n, s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx, sy = si + a, sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx, by = bi + a, bj + b\n",
    "                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:\n",
    "                        continue\n",
    "                    vis[f(sx, sy)][f(bx, by)] = True\n",
    "                    q.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                elif not vis[f(sx, sy)][f(bi, bj)]:\n",
    "                    vis[f(sx, sy)][f(bi, bj)] = True\n",
    "                    q.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def f(i: int, j: int) -> int:\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n and grid[i][j] != \"#\"\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == \"S\":\n",
    "                    si, sj = i, j\n",
    "                elif c == \"B\":\n",
    "                    bi, bj = i, j\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(f(si, sj), f(bi, bj), 0)])\n",
    "        vis = [[False] * (m * n) for _ in range(m * n)]\n",
    "        vis[f(si, sj)][f(bi, bj)] = True\n",
    "        while q:\n",
    "            s, b, d = q.popleft()\n",
    "            bi, bj = b // n, b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si, sj = s // n, s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx, sy = si + a, sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx, by = bi + a, bj + b\n",
    "                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:\n",
    "                        continue\n",
    "                    vis[f(sx, sy)][f(bx, by)] = True\n",
    "                    q.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                elif not vis[f(sx, sy)][f(bi, bj)]:\n",
    "                    vis[f(sx, sy)][f(bi, bj)] = True\n",
    "                    q.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def f(i: int, j: int) -> int:\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n and grid[i][j] != \"#\"\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == \"S\":\n",
    "                    si, sj = i, j\n",
    "                elif c == \"B\":\n",
    "                    bi, bj = i, j\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(f(si, sj), f(bi, bj), 0)])\n",
    "        vis = [[False] * (m * n) for _ in range(m * n)]\n",
    "        vis[f(si, sj)][f(bi, bj)] = True\n",
    "        while q:\n",
    "            s, b, d = q.popleft()\n",
    "            bi, bj = b // n, b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si, sj = s // n, s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx, sy = si + a, sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx, by = bi + a, bj + b\n",
    "                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:\n",
    "                        continue\n",
    "                    vis[f(sx, sy)][f(bx, by)] = True\n",
    "                    q.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                elif not vis[f(sx, sy)][f(bi, bj)]:\n",
    "                    vis[f(sx, sy)][f(bi, bj)] = True\n",
    "                    q.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def f(i: int, j: int) -> int:\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n and grid[i][j] != \"#\"\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == \"S\":\n",
    "                    si, sj = i, j\n",
    "                elif c == \"B\":\n",
    "                    bi, bj = i, j\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(f(si, sj), f(bi, bj), 0)])\n",
    "        vis = [[False] * (m * n) for _ in range(m * n)]\n",
    "        vis[f(si, sj)][f(bi, bj)] = True\n",
    "        while q:\n",
    "            s, b, d = q.popleft()\n",
    "            bi, bj = b // n, b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si, sj = s // n, s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx, sy = si + a, sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx, by = bi + a, bj + b\n",
    "                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:\n",
    "                        continue\n",
    "                    vis[f(sx, sy)][f(bx, by)] = True\n",
    "                    q.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                elif not vis[f(sx, sy)][f(bi, bj)]:\n",
    "                    vis[f(sx, sy)][f(bi, bj)] = True\n",
    "                    q.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def f(i: int, j: int) -> int:\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i: int, j: int) -> bool:\n",
    "            return 0 <= i < m and 0 <= j < n and grid[i][j] != \"#\"\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == \"S\":\n",
    "                    si, sj = i, j\n",
    "                elif c == \"B\":\n",
    "                    bi, bj = i, j\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(f(si, sj), f(bi, bj), 0)])\n",
    "        vis = [[False] * (m * n) for _ in range(m * n)]\n",
    "        vis[f(si, sj)][f(bi, bj)] = True\n",
    "        while q:\n",
    "            s, b, d = q.popleft()\n",
    "            bi, bj = b // n, b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si, sj = s // n, s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx, sy = si + a, sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx, by = bi + a, bj + b\n",
    "                    if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:\n",
    "                        continue\n",
    "                    vis[f(sx, sy)][f(bx, by)] = True\n",
    "                    q.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                elif not vis[f(sx, sy)][f(bi, bj)]:\n",
    "                    vis[f(sx, sy)][f(bi, bj)] = True\n",
    "                    q.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        s_pos, b_pos, t_pos = None, None, None\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'S':\n",
    "                    s_pos = (i, j)\n",
    "                    grid[i][j] = '.'\n",
    "                elif grid[i][j] == 'B':\n",
    "                    b_pos = (i, j)\n",
    "                    grid[i][j] = '.'\n",
    "                elif grid[i][j] == 'T':\n",
    "                    t_pos = (i, j)\n",
    "                    grid[i][j] = '.'\n",
    "\n",
    "        q = Queue()\n",
    "        vis = [[False] * (m * n) for _ in range(m * n)]\n",
    "        step = 0\n",
    "\n",
    "        dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)]\n",
    "        q.put((s_pos, b_pos))\n",
    "\n",
    "        while not q.empty():\n",
    "            q1 = Queue()\n",
    "            while not q.empty():\n",
    "                (cur_p, cur_b) = q.get()\n",
    "                x = cur_p[0] * n + cur_p[1]\n",
    "                y = cur_b[0] * n + cur_b[1]\n",
    "                if vis[x][y]:\n",
    "                    continue\n",
    "\n",
    "                vis[x][y] = True    \n",
    "                if cur_b == t_pos:\n",
    "                    return step\n",
    "                else:\n",
    "                    for d in dirs:\n",
    "                        p_nx = cur_p[0] + d[0]\n",
    "                        p_ny = cur_p[1] + d[1]\n",
    "                        if p_nx < 0 or p_nx >= m or p_ny < 0 or p_ny >= n:\n",
    "                            continue\n",
    "                        elif grid[p_nx][p_ny] == '#':\n",
    "                            continue\n",
    "\n",
    "                        nx = p_nx * n + p_ny\n",
    "                        if p_nx == cur_b[0] and p_ny == cur_b[1]:\n",
    "                            b_nx = cur_b[0] + d[0]\n",
    "                            b_ny = cur_b[1] + d[1]\n",
    "                            if b_nx < 0 or b_nx >= m or b_ny < 0 or b_ny >= n:\n",
    "                                continue\n",
    "                            elif grid[b_nx][b_ny] == '#':\n",
    "                                continue\n",
    "\n",
    "                            ny = b_nx * n + b_ny\n",
    "                            if not vis[nx][ny]:\n",
    "                                q1.put(((p_nx, p_ny), (b_nx, b_ny)))\n",
    "\n",
    "                        elif not vis[nx][y]:\n",
    "                            q.put(((p_nx, p_ny), cur_b))\n",
    "\n",
    "            step += 1\n",
    "            q = q1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0]) \n",
    "        sx, sy, bx, by = -1, -1, -1, -1 # 玩家、箱子的初始位置 \n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S': \n",
    "                    sx = x\n",
    "                    sy = y \n",
    "                elif grid[x][y] == 'B': \n",
    "                    bx = x\n",
    "                    by = y    \n",
    "                elif grid[x][y] == 'T' :\n",
    "                    tx = x\n",
    "                    ty = y   \n",
    "        # 不越界且不在墙上 \n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#') \n",
    "        d = [0, -1, 0, 1, 0]\n",
    "\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)] \n",
    "        dp[sx * n + sy][bx * n + by] = 0 # 初始状态的推动次数为 0 \n",
    "        q = deque([(sx * n + sy, bx * n + by)]) \n",
    "        while q:\n",
    "            q1 = deque() \n",
    "            while q: \n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n \n",
    "                bx1, by1 = b1 // n, b1 % n \n",
    "                if grid[bx1][by1] == 'T': # 箱子已被推到目标处 \n",
    "                    return dp[s1][b1]\n",
    "                for i in range(4): # 玩家向四个方向移动到另一个状态\n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]  \n",
    "                    s2 = sx2 * n + sy2 \n",
    "                    if not ok(sx2, sy2): # 玩家位置不合法\n",
    "                        continue \n",
    "                    if sx2 == bx1 and sy2 == by1: # 推动箱子\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1] \n",
    "                        b2 = bx2 * n + by2 \n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1: # 箱子位置不合法或状态已访问\n",
    "                            continue \n",
    "                        dp[s2][b2] = dp[s1][b1] + 1 \n",
    "                        q1.append((s2, b2)) \n",
    "                    else: \n",
    "                        if dp[s2][b1] <= dp[s1][b1]: # 状态已访问 \n",
    "                            continue \n",
    "                        dp[s2][b1] = dp[s1][b1] \n",
    "                        q.append((s2, b1)) \n",
    "            q, q1 = q1, q \n",
    "        return -1 \n",
    "\n",
    "\n",
    "\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        sx, sy, bx, by = None, None, None, None # 玩家、箱子的初始位置\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S':\n",
    "                    sx = x\n",
    "                    sy = y\n",
    "                elif grid[x][y] == 'B':\n",
    "                    bx = x\n",
    "                    by = y\n",
    "\n",
    "        # 不越界且不在墙上\n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\n",
    "\n",
    "        d = [0, -1, 0, 1, 0]\n",
    "\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\n",
    "        dp[sx * n + sy][bx * n + by] = 0 # 初始状态的推动次数为 0\n",
    "        q = deque([(sx * n + sy, bx * n + by)])\n",
    "        while q:\n",
    "            q1 = deque()\n",
    "            while q:\n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n\n",
    "                bx1, by1 = b1 // n, b1 % n\n",
    "                if grid[bx1][by1] == 'T': # 箱子已被推到目标处\n",
    "                    return dp[s1][b1]\n",
    "                for i in range(4): # 玩家向四个方向移动到另一个状态\n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]\n",
    "                    s2 = sx2 * n + sy2\n",
    "                    if not ok(sx2, sy2): # 玩家位置不合法\n",
    "                        continue\n",
    "                    if sx2 == bx1 and sy2 == by1: # 推动箱子\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1]\n",
    "                        b2 = bx2 * n + by2\n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1: # 箱子位置不合法 或 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\n",
    "                        q1.append((s2, b2))\n",
    "                    else:\n",
    "                        if dp[s2][b1] <= dp[s1][b1]: # 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b1] = dp[s1][b1]\n",
    "                        q.append((s2, b1))\n",
    "            q, q1 = q1, q\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from itertools import pairwise\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: list[list[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        visited = [[False] * (m * n) for _ in range(m * n)]\n",
    "\n",
    "        def f(i, j):\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i, j):\n",
    "            return (0 <= i < m) and (0 <= j < n) and (grid[i][j] != \"#\")\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"S\":\n",
    "                    si = i\n",
    "                    sj = j\n",
    "                elif grid[i][j] == \"B\":\n",
    "                    bi = i\n",
    "                    bj = j\n",
    "\n",
    "        que = deque()\n",
    "        que += ([(f(si, sj), f(bi, bj), 0)])\n",
    "        while que:\n",
    "            s, b, d = que.popleft()\n",
    "            bi = b // n\n",
    "            bj = b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si = s // n\n",
    "            sj = s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx = si + a\n",
    "                sy = sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx = bi + a\n",
    "                    by = bj + b\n",
    "                    if not check(bx, by):\n",
    "                        continue\n",
    "                    visited[f(sx, sy)][f(bx, by)] = True\n",
    "                    que.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                else:\n",
    "                    if not visited[f(sx, sy)][f(bi, bj)]:\n",
    "                        visited[f(sx, sy)][f(bi, bj)] = True\n",
    "                        que.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    grid = [[\"#\", \"#\", \"#\", \"#\", \"#\", \"#\"], [\"#\", \"T\", \".\", \".\", \"#\", \"#\"], [\"#\", \".\", \"#\", \"B\", \".\", \"#\"],\n",
    "            [\"#\", \".\", \".\", \".\", \".\", \"#\"], [\"#\", \".\", \".\", \".\", \"S\", \"#\"], [\"#\", \"#\", \"#\", \"#\", \"#\", \"#\"]]\n",
    "    print(obj.minPushBox(grid))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from itertools import pairwise\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: list[list[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        visited = [[False] * (m * n) for _ in range(m * n)]\n",
    "\n",
    "        def f(i, j):\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i, j):\n",
    "            return (0 <= i < m) and (0 <= j < n) and (grid[i][j] != \"#\")\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"S\":\n",
    "                    si = i\n",
    "                    sj = j\n",
    "                elif grid[i][j] == \"B\":\n",
    "                    bi = i\n",
    "                    bj = j\n",
    "\n",
    "        que = deque()\n",
    "        que += ([(f(si, sj), f(bi, bj), 0)])\n",
    "        while que:\n",
    "            s, b, d = que.popleft()\n",
    "            bi = b // n\n",
    "            bj = b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si = s // n\n",
    "            sj = s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx = si + a\n",
    "                sy = sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx = bi + a\n",
    "                    by = bj + b\n",
    "                    if not check(bx, by):\n",
    "                        continue\n",
    "                    visited[f(sx, sy)][f(bx, by)] = True\n",
    "                    que.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                else:\n",
    "                    if not visited[f(sx, sy)][f(bi, bj)]:\n",
    "                        visited[f(sx, sy)][f(bi, bj)] = True\n",
    "                        que.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    grid = [[\"#\", \"#\", \"#\", \"#\", \"#\", \"#\"], [\"#\", \"T\", \".\", \".\", \"#\", \"#\"], [\"#\", \".\", \"#\", \"B\", \".\", \"#\"],\n",
    "            [\"#\", \".\", \".\", \".\", \".\", \"#\"], [\"#\", \".\", \".\", \".\", \"S\", \"#\"], [\"#\", \"#\", \"#\", \"#\", \"#\", \"#\"]]\n",
    "    print(obj.minPushBox(grid))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        sx, sy, bx, by = None, None, None, None # 玩家、箱子的初始位置\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S':\n",
    "                    sx = x\n",
    "                    sy = y\n",
    "                elif grid[x][y] == 'B':\n",
    "                    bx = x\n",
    "                    by = y\n",
    "\n",
    "        # 不越界且不在墙上\n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\n",
    "\n",
    "        d = [0, -1, 0, 1, 0]\n",
    "\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\n",
    "        dp[sx * n + sy][bx * n + by] = 0 # 初始状态的推动次数为 0\n",
    "        q = deque([(sx * n + sy, bx * n + by)])\n",
    "        while q:\n",
    "            q1 = deque()\n",
    "            while q:\n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n\n",
    "                bx1, by1 = b1 // n, b1 % n\n",
    "                if grid[bx1][by1] == 'T': # 箱子已被推到目标处\n",
    "                    return dp[s1][b1]\n",
    "                for i in range(4): # 玩家向四个方向移动到另一个状态\n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]\n",
    "                    s2 = sx2 * n + sy2\n",
    "                    if not ok(sx2, sy2): # 玩家位置不合法\n",
    "                        continue\n",
    "                    if sx2 == bx1 and sy2 == by1: # 推动箱子\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1]\n",
    "                        b2 = bx2 * n + by2\n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1: # 箱子位置不合法 或 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\n",
    "                        q1.append((s2, b2))\n",
    "                    else:\n",
    "                        if dp[s2][b1] <= dp[s1][b1]: # 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b1] = dp[s1][b1]\n",
    "                        q.append((s2, b1))\n",
    "            q, q1 = q1, q\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        height = len(grid)\n",
    "        width = len(grid[0])\n",
    "        start_y,start_x = 0,0\n",
    "        box_y,box_x = 0,0\n",
    "        dest_y,dest_x = 0,0\n",
    "        for y in range(height):\n",
    "            for x in range(width):\n",
    "                if grid[y][x]==\"S\":\n",
    "                    start_y,start_x = y,x\n",
    "                if grid[y][x]==\"B\":\n",
    "                    box_y,box_x = y,x\n",
    "                if grid[y][x]==\"T\":\n",
    "                    dest_y,dest_x = y,x\n",
    "        def state_ok(y,x):\n",
    "            if 0<=y<height and 0<=x<width and grid[y][x]!=\"#\":\n",
    "                return True\n",
    "            return False\n",
    "        dp = [[-1]*(height*width) for _ in range(height*width)]\n",
    "        dp[start_y*width+start_x][box_y*width+box_x]=0\n",
    "        q = [(start_y,start_x,box_y,box_x)]\n",
    "        add_pos = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        while(q):\n",
    "            q_next = []\n",
    "            for start_y,start_x,box_y,box_x in q:\n",
    "                for add_y,add_x in add_pos:\n",
    "                    end_y = start_y + add_y\n",
    "                    end_x = start_x + add_x\n",
    "                    if not state_ok(end_y,end_x):\n",
    "                        continue\n",
    "                    if dp[end_y*width+end_x][box_y*width+box_x]!=-1:\n",
    "                        # 以及visit过了\n",
    "                        continue\n",
    "                    if end_y==box_y and end_x==box_x:\n",
    "                        #移动箱子\n",
    "                        box_y_next = box_y+add_y\n",
    "                        box_x_next = box_x+add_x\n",
    "                        if not state_ok(box_y_next,box_x_next):\n",
    "                            continue\n",
    "                        if box_x_next==dest_x and box_y_next==dest_y:\n",
    "                            return dp[start_y*width+start_x][box_y*width+box_x]+1\n",
    "                        if dp[end_y*width+end_x][box_y_next*width+box_x_next]==-1:\n",
    "                            dp[end_y*width+end_x][box_y_next*width+box_x_next] = dp[start_y*width+start_x][box_y*width+box_x] + 1 \n",
    "                            q_next.append((end_y,end_x,box_y_next,box_x_next))\n",
    "                    else:\n",
    "                        dp[end_y*width+end_x][box_y*width+box_x] = dp[start_y*width+start_x][box_y*width+box_x]\n",
    "                        q.append((end_y,end_x,box_y,box_x))\n",
    "            q = q_next\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        sx, sy, bx, by = None, None, None, None\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S':\n",
    "                    sx = x\n",
    "                    sy = y\n",
    "                elif grid[x][y] == 'B':\n",
    "                    bx = x\n",
    "                    by = y\n",
    "\n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\n",
    "        \n",
    "        d = [0, -1, 0, 1, 0]\n",
    "    \n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\n",
    "        dp[sx * n + sy][bx * n + by] = 0\n",
    "        q = deque([(sx * n + sy, bx * n + by)])\n",
    "        while q:\n",
    "            q1 = deque()\n",
    "            while q:\n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n\n",
    "                bx1, by1 = b1 // n, b1 % n\n",
    "                if grid[bx1][by1] == 'T':\n",
    "                    return dp[s1][b1]\n",
    "                for i in range(4):\n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]\n",
    "                    s2 = sx2 * n + sy2\n",
    "                    if not ok(sx2, sy2):\n",
    "                        continue\n",
    "                    if sx2 == bx1 and sy2 == by1:\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1]\n",
    "                        b2 = bx2 * n + by2\n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1:\n",
    "                            continue\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\n",
    "                        q1.append((s2, b2))\n",
    "                    else:\n",
    "                        if dp[s2][b1] <= dp[s1][b1]:\n",
    "                            continue\n",
    "                        dp[s2][b1] = dp[s1][b1]\n",
    "                        q.append((s2, b1))\n",
    "            q, q1 = q1, q\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        sx, sy, bx, by = None, None, None, None # 玩家、箱子的初始位置\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S':\n",
    "                    sx = x\n",
    "                    sy = y\n",
    "                elif grid[x][y] == 'B':\n",
    "                    bx = x\n",
    "                    by = y\n",
    "\n",
    "        # 不越界且不在墙上\n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\n",
    "\n",
    "        d = [0, -1, 0, 1, 0]\n",
    "\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\n",
    "        dp[sx * n + sy][bx * n + by] = 0 # 初始状态的推动次数为 0\n",
    "        q = deque([(sx * n + sy, bx * n + by)])\n",
    "        while q:\n",
    "            q1 = deque()\n",
    "            while q:\n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n\n",
    "                bx1, by1 = b1 // n, b1 % n\n",
    "                if grid[bx1][by1] == 'T': # 箱子已被推到目标处\n",
    "                    return dp[s1][b1]\n",
    "                for i in range(4): # 玩家向四个方向移动到另一个状态\n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]\n",
    "                    s2 = sx2 * n + sy2\n",
    "                    if not ok(sx2, sy2): # 玩家位置不合法\n",
    "                        continue\n",
    "                    if sx2 == bx1 and sy2 == by1: # 推动箱子\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1]\n",
    "                        b2 = bx2 * n + by2\n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1: # 箱子位置不合法 或 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\n",
    "                        q1.append((s2, b2))\n",
    "                    else:\n",
    "                        if dp[s2][b1] <= dp[s1][b1]: # 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b1] = dp[s1][b1]\n",
    "                        q.append((s2, b1))\n",
    "            q, q1 = q1, q\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        sx, sy, bx, by = None, None, None, None # 玩家、箱子的初始位置\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S':\n",
    "                    sx = x\n",
    "                    sy = y\n",
    "                elif grid[x][y] == 'B':\n",
    "                    bx = x\n",
    "                    by = y\n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\n",
    "\n",
    "        d = [0, -1, 0, 1, 0]\n",
    "        def distance(p1,p2):\n",
    "            if ok(p2[0],p2[1]):\n",
    "                return abs(p2[0]-p1[0])+abs(p2[1]-p1[1])\n",
    "            else:\n",
    "                return float('inf')\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\n",
    "        dp[sx * n + sy][bx * n + by] = 0 \n",
    "        q = deque([(sx * n + sy, bx * n + by)])\n",
    "        while q:\n",
    "            q1 = deque()\n",
    "            while q:\n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n\n",
    "                bx1, by1 = b1 // n, b1 % n\n",
    "                if grid[bx1][by1] == 'T': \n",
    "                    return dp[s1][b1]\n",
    "                max = distance([sx1,sy1],[bx1,by1])\n",
    "                for i in range(4): \n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]\n",
    "                    s2 = sx2 * n + sy2\n",
    "                    if not ok(sx2, sy2):\n",
    "                        continue\n",
    "                    \n",
    "                    if sx2 == bx1 and sy2 == by1:\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1]\n",
    "                        b2 = bx2 * n + by2\n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1:\n",
    "                            continue\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\n",
    "                        q1.append((s2, b2))\n",
    "                    else:\n",
    "                        if dp[s2][b1] <= dp[s1][b1]:\n",
    "                            continue\n",
    "                        dp[s2][b1] = dp[s1][b1]\n",
    "                        q.append((s2, b1))\n",
    "            q, q1 = q1, q\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0]) \n",
    "        sx, sy, bx, by = -1, -1, -1, -1 # 玩家、箱子的初始位置 \n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S': \n",
    "                    sx = x\n",
    "                    sy = y \n",
    "                elif grid[x][y] == 'B': \n",
    "                    bx = x\n",
    "                    by = y       \n",
    "        # 不越界且不在墙上 \n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#') \n",
    "        d = [0, -1, 0, 1, 0]\n",
    "\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)] \n",
    "        dp[sx * n + sy][bx * n + by] = 0 # 初始状态的推动次数为 0 \n",
    "        q = deque([(sx * n + sy, bx * n + by)]) \n",
    "        while q:\n",
    "            q1 = deque() \n",
    "            while q: \n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n \n",
    "                bx1, by1 = b1 // n, b1 % n \n",
    "                if grid[bx1][by1] == 'T': # 箱子已被推到目标处 \n",
    "                    return dp[s1][b1]\n",
    "                for i in range(4): # 玩家向四个方向移动到另一个状态\n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]  \n",
    "                    s2 = sx2 * n + sy2 \n",
    "                    if not ok(sx2, sy2): # 玩家位置不合法\n",
    "                        continue \n",
    "                    if sx2 == bx1 and sy2 == by1: # 推动箱子\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1] \n",
    "                        b2 = bx2 * n + by2 \n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1: # 箱子位置不合法或状态已访问\n",
    "                            continue \n",
    "                        dp[s2][b2] = dp[s1][b1] + 1 \n",
    "                        q1.append((s2, b2)) \n",
    "                    else: \n",
    "                        if dp[s2][b1] <= dp[s1][b1]: # 状态已访问 \n",
    "                            continue \n",
    "                        dp[s2][b1] = dp[s1][b1] \n",
    "                        q.append((s2, b1)) \n",
    "            q, q1 = q1, q \n",
    "        return -1 \n",
    "\n",
    "\n",
    "\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        # 关键要点?\n",
    "        # 1. 需要记录状态\n",
    "        # 2. 怎么设计移动，只记录用户移动是更好的\n",
    "        if not grid:\n",
    "            return -1\n",
    "        width = len(grid[0])\n",
    "        height = len(grid)\n",
    "        \n",
    "        def validPosition(x, y):\n",
    "            if 0<=x<height and 0<=y<width and grid[x][y] != '#':\n",
    "                return True\n",
    "\n",
    "        visited = [[False]*(width*height) for i in range(width*height)]\n",
    "\n",
    "        def isVisited(hx, hy, bx, by):\n",
    "            return visited[hx * width +  hy][bx*width + by]\n",
    "        \n",
    "        hx, hy, bx, by = 0, 0, 0, 0\n",
    "\n",
    "        terminalX, terminalY = 0, 0\n",
    "\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                if grid[i][j] == 'S':\n",
    "                    hx, hy = i, j\n",
    "                if grid[i][j] == 'B':\n",
    "                    bx, by = i, j\n",
    "                if grid[i][j] == 'T':\n",
    "                    terminalX, terminalY = i, j\n",
    "        q = [(hx, hy, bx, by, 0)]\n",
    "        # 注意初始化第一个位置为true\n",
    "        visited[hx*width + hy][bx*width+by] = True\n",
    "\n",
    "        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "\n",
    "        minstep = inf\n",
    "\n",
    "        while q:\n",
    "            hx,hy,bx,by,step = q.pop(0)\n",
    "\n",
    "            # if is terminal\n",
    "            if bx == terminalX and by == terminalY:\n",
    "                minstep = min(minstep, step )\n",
    "                return minstep\n",
    "\n",
    "            for d in range(4):\n",
    "                hx1, hy1 = hx + directions[d][0], hy + directions[d][1]\n",
    "                if validPosition(hx1, hy1):\n",
    "                    # if come into box\n",
    "                    if hx1 == bx and hy1 == by:\n",
    "                        bx1, by1 = bx + directions[d][0], by + directions[d][1]\n",
    "                        if validPosition(bx1, by1) and not isVisited(hx1, hy1, bx1, by1):\n",
    "                            # can push box\n",
    "                            q.append((hx1, hy1, bx1, by1, step + 1))\n",
    "                            visited[hx1* width + hy1][bx1*width + by1] = True\n",
    "\n",
    "\n",
    "                    else:\n",
    "                        # not come into box\n",
    "                        if not isVisited(hx1, hy1, bx, by):\n",
    "                            visited[hx1 * width + hy1][bx * width + by] = True\n",
    "                            # 为啥这里要appendleft？，\n",
    "                            q.insert(0, (hx1, hy1, bx, by, step))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        sx, sy, bx, by = None, None, None, None # 玩家、箱子的初始位置\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 'S':\n",
    "                    sx = x\n",
    "                    sy = y\n",
    "                elif grid[x][y] == 'B':\n",
    "                    bx = x\n",
    "                    by = y\n",
    "\n",
    "        # 不越界且不在墙上\n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\n",
    "\n",
    "        d = [0, -1, 0, 1, 0]\n",
    "\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\n",
    "        dp[sx * n + sy][bx * n + by] = 0 # 初始状态的推动次数为 0\n",
    "        q = deque([(sx * n + sy, bx * n + by)])\n",
    "        while q:\n",
    "            q1 = deque()\n",
    "            while q:\n",
    "                s1, b1 = q.popleft()\n",
    "                sx1, sy1 = s1 // n, s1 % n\n",
    "                bx1, by1 = b1 // n, b1 % n\n",
    "                if grid[bx1][by1] == 'T': # 箱子已被推到目标处\n",
    "                    return dp[s1][b1]\n",
    "                for i in range(4): # 玩家向四个方向移动到另一个状态\n",
    "                    sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]\n",
    "                    s2 = sx2 * n + sy2\n",
    "                    if not ok(sx2, sy2): # 玩家位置不合法\n",
    "                        continue\n",
    "                    if sx2 == bx1 and sy2 == by1: # 推动箱子\n",
    "                        bx2, by2 = bx1 + d[i], by1 + d[i + 1]\n",
    "                        b2 = bx2 * n + by2\n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1: # 箱子位置不合法 或 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\n",
    "                        q1.append((s2, b2))\n",
    "                    else:\n",
    "                        if dp[s2][b1] <= dp[s1][b1]: # 状态已访问\n",
    "                            continue\n",
    "                        dp[s2][b1] = dp[s1][b1]\n",
    "                        q.append((s2, b1))\n",
    "            q, q1 = q1, q\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\r\n",
    "        m = len(grid)\r\n",
    "        n = len(grid[0])\r\n",
    "\r\n",
    "        sx = None\r\n",
    "        sy = None\r\n",
    "        bx = None\r\n",
    "        by = None\r\n",
    "\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == \"S\":\r\n",
    "                    sx = i\r\n",
    "                    sy = j\r\n",
    "                elif grid[i][j] == \"B\":\r\n",
    "                    bx = i\r\n",
    "                    by = j\r\n",
    "\r\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\r\n",
    "        q = collections.deque([(sx * n + sy, bx * n + by)])\r\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\r\n",
    "        dp[sx * n + sy][bx * n + by] = 0\r\n",
    "\r\n",
    "        def validposistion(x, y):\r\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\r\n",
    "\r\n",
    "        while q:\r\n",
    "            q1 = collections.deque()\r\n",
    "            while q:\r\n",
    "                s1, b1 = q.popleft()\r\n",
    "                sx1 = s1 // n\r\n",
    "                sy1 = s1 % n\r\n",
    "                bx1 = b1 // n\r\n",
    "                by1 = b1 % n\r\n",
    "\r\n",
    "                if grid[bx1][by1] == \"T\":\r\n",
    "                    return dp[s1][b1]\r\n",
    "\r\n",
    "                for i in range(4):\r\n",
    "                    sx2 = sx1 + direction[i][0]\r\n",
    "                    sy2 = sy1 + direction[i][1]\r\n",
    "                    s2 = sx2 * n + sy2\r\n",
    "                    if not validposistion(sx2, sy2):\r\n",
    "                        continue\r\n",
    "\r\n",
    "                    if sx2 == bx1 and sy2 == by1:\r\n",
    "                        bx2 = bx1 + direction[i][0]\r\n",
    "                        by2 = by1 + direction[i][1]\r\n",
    "                        b2 = bx2 * n + by2\r\n",
    "                        if not validposistion(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1:\r\n",
    "                            continue\r\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\r\n",
    "                        q1.append((s2, b2))\r\n",
    "                    else:\r\n",
    "                        if dp[s2][b1] <= dp[s1][b1]:\r\n",
    "                            continue\r\n",
    "                        else:\r\n",
    "                            dp[s2][b1] = dp[s1][b1]\r\n",
    "                            q.append((s2, b1))\r\n",
    "            q, q1 = q1, q\r\n",
    "\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        def ok(x, y):\n",
    "            return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')\n",
    "\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 先找人和箱子\n",
    "        sx, sy, bx, by = [None] * 4\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'S':\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j] == 'B':\n",
    "                    bx, by = i, j\n",
    "        # 太狠了, 为了memo两个格子\n",
    "        dp = [[float('inf')] * (m * n) for _ in range(m * n)]\n",
    "        dp[sx * n + sy][bx * n + by] = 0\n",
    "        q = deque([(sx * n + sy, bx * n + by)])\n",
    "\n",
    "        while q:\n",
    "            q1 = deque()\n",
    "            while q:\n",
    "                s1, b1 = q.popleft()\n",
    "                # 复原\n",
    "                sx1, sy1 = s1 // n, s1 % n\n",
    "                bx1, by1 = b1 // n, b1 % n\n",
    "                if grid[bx1][by1] == 'T':\n",
    "                    return dp[s1][b1]\n",
    "                for dx, dy in dirs:\n",
    "                    sx2, sy2 = sx1 + dx, sy1 + dy\n",
    "                    s2 = sx2 * n + sy2\n",
    "                    if not ok(sx2, sy2):\n",
    "                        continue\n",
    "                    if sx2 == bx1 and sy2 == by1:\n",
    "                        # 推动箱子\n",
    "                        bx2, by2 = bx1 + dx, by1 + dy\n",
    "                        b2 = bx2 * n + by2\n",
    "                        if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1:\n",
    "                            # 撞墙或者已经访问\n",
    "                            continue\n",
    "                        dp[s2][b2] = dp[s1][b1] + 1\n",
    "                        # 加到q1别走太深\n",
    "                        q1.append((s2, b2))\n",
    "                    else:\n",
    "                        if dp[s2][b1] <= dp[s1][b1]:\n",
    "                            continue\n",
    "                        dp[s2][b1] = dp[s1][b1]\n",
    "                        q.append((s2, b1))\n",
    "            q, q1 = q1, q\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        S, T, B = None, None, None\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'S': S = i * n + j\n",
    "                if grid[i][j] == 'T': T = i * n + j\n",
    "                if grid[i][j] == 'B': B = i * n + j\n",
    "\n",
    "        dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n",
    "\n",
    "        dist = [[-1] * (m * n) for _ in range(m * n)]\n",
    "        dist[S][B] = 0\n",
    "\n",
    "        Q = collections.deque()\n",
    "        Q.append((S, B))\n",
    "\n",
    "        while Q:\n",
    "            player, box = Q.popleft()\n",
    "            D = dist[player][box]\n",
    "            if box == T: return D\n",
    "\n",
    "            px, py, bx, by = player // n, player % n, box // n, box % n\n",
    "            print(px, py, bx, by)\n",
    "            for dx, dy in dirs:\n",
    "                newPx, newPy = px + dx, py + dy\n",
    "                print(1)\n",
    "                if not (0 <= newPx < m and 0 <= newPy < n): continue\n",
    "                print(2)\n",
    "                if grid[newPx][newPy] == '#': continue\n",
    "\n",
    "                newPlayer = newPx * n + newPy\n",
    "                moved = newPlayer == box\n",
    "\n",
    "                if moved:\n",
    "                    newBx, newBy = bx + dx, by + dy\n",
    "                    print(3)\n",
    "                    if not (0 <= newBx < m and 0 <= newBy < n) or grid[newBx][newBy] == '#': continue\n",
    "                    newBox = newBx * n + newBy\n",
    "                else:\n",
    "                    newBox = box\n",
    "\n",
    "                if dist[newPlayer][newBox] != -1: continue\n",
    "\n",
    "                if moved:\n",
    "                    Q.append((newPlayer, newBox))\n",
    "                    dist[newPlayer][newBox] = D + 1\n",
    "                else:\n",
    "                    Q.appendleft((newPlayer, newBox))\n",
    "                    dist[newPlayer][newBox] = D\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from itertools import pairwise\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: list[list[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[False] * (m * n) for _ in range(m * n)]\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        print(visited)\n",
    "\n",
    "        def f(i, j):\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i, j):\n",
    "            return (0 <= i < m) and (0 <= j < n) and (grid[i][j] != \"#\")\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"S\":\n",
    "                    si = i\n",
    "                    sj = j\n",
    "                if grid[i][j] == \"B\":\n",
    "                    bi = i\n",
    "                    bj = j\n",
    "\n",
    "        que = deque()\n",
    "        que += ([(f(si, sj), f(bi, bj), 0)])\n",
    "        print(que)\n",
    "\n",
    "        while que:\n",
    "            s, b, d = que.popleft()\n",
    "            bi = b // n\n",
    "            bj = b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si = s // n\n",
    "            sj = s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx = si + a\n",
    "                sy = sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx = bi + a\n",
    "                    by = bj + b\n",
    "                    if not check(bx, by):\n",
    "                        continue\n",
    "                    visited[f(sx, sy)][f(bx, by)] = True\n",
    "                    que.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                else:\n",
    "                    if not visited[f(sx, sy)][f(bi, bj)]:\n",
    "                        visited[f(sx, sy)][f(bi, bj)] = True\n",
    "                        que.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    grid = [[\"#\", \"#\", \"#\", \"#\", \"#\", \"#\"], [\"#\", \"T\", \".\", \".\", \"#\", \"#\"], [\"#\", \".\", \"#\", \"B\", \".\", \"#\"],\n",
    "            [\"#\", \".\", \".\", \".\", \".\", \"#\"], [\"#\", \".\", \".\", \".\", \"S\", \"#\"], [\"#\", \"#\", \"#\", \"#\", \"#\", \"#\"]]\n",
    "    print(obj.minPushBox(grid))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from itertools import pairwise\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: list[list[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        visited = [[False] * (m * n) for _ in range(m * n)]\n",
    "        print(visited)\n",
    "\n",
    "        def f(i, j):\n",
    "            return i * n + j\n",
    "\n",
    "        def check(i, j):\n",
    "            return (0 <= i < m) and (0 <= j < n) and (grid[i][j] != \"#\")\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"B\":\n",
    "                    bi = i\n",
    "                    bj = j\n",
    "                elif grid[i][j] == \"S\":\n",
    "                    si = i\n",
    "                    sj = j\n",
    "\n",
    "        que = deque()\n",
    "        que += [(f(si, sj), f(bi, bj), 0)]\n",
    "        print(que)\n",
    "        while que:\n",
    "            s, b, d = que.popleft()\n",
    "            bi = b // n\n",
    "            bj = b % n\n",
    "            if grid[bi][bj] == \"T\":\n",
    "                return d\n",
    "            si = s // n\n",
    "            sj = s % n\n",
    "            for a, b in pairwise(dirs):\n",
    "                sx = si + a\n",
    "                sy = sj + b\n",
    "                if not check(sx, sy):\n",
    "                    continue\n",
    "                if sx == bi and sy == bj:\n",
    "                    bx = bi + a\n",
    "                    by = bj + b\n",
    "                    if not check(bx, by) or visited[f(sx, sy)][f(bx, by)]:\n",
    "                        continue\n",
    "                    visited[f(sx, sy)][f(bx, by)] = True\n",
    "                    que.append((f(sx, sy), f(bx, by), d + 1))\n",
    "                elif not visited[f(sx, sy)][f(bi, bj)]:\n",
    "                    visited[f(sx, sy)][f(bi, bj)] = True\n",
    "                    que.appendleft((f(sx, sy), f(bi, bj), d))\n",
    "        return -1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    grid = [[\"#\", \".\", \".\", \"#\", \"#\", \"#\", \"#\", \"#\"], [\"#\", \".\", \".\", \"T\", \"#\", \".\", \".\", \"#\"],\n",
    "            [\"#\", \".\", \".\", \".\", \"#\", \"B\", \".\", \"#\"], [\"#\", \".\", \".\", \".\", \".\", \".\", \".\", \"#\"],\n",
    "            [\"#\", \".\", \".\", \".\", \"#\", \".\", \"S\", \"#\"], [\"#\", \".\", \".\", \"#\", \"#\", \"#\", \"#\", \"#\"]]\n",
    "\n",
    "    print(obj.minPushBox(grid))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"S\":\n",
    "                    s=(i,j)\n",
    "                if grid[i][j]==\"B\": \n",
    "                    b=(i,j) \n",
    "                if grid[i][j]==\"T\":\n",
    "                    t=(i,j)\n",
    "        q=[]\n",
    "        visited=set()\n",
    "        visited.add((b[0],b[1],s[0],s[1]))\n",
    "        q.append((b[0],b[1],s[0],s[1],0))\n",
    "        while len(q)>0:\n",
    "            bx,by,px,py,counter=q.pop(0)\n",
    "            if bx==t[0] and by==t[1]:\n",
    "                return counter\n",
    "            for i,j in [(px-1,py),(px+1,py),(px,py-1),(px,py+1)]:\n",
    "                if 0<=i<m and 0<=j<n and grid[i][j]!=\"#\" and (i,j)!=(bx,by):\n",
    "                    if (bx,by,i,j) not in visited:\n",
    "                        q=[(bx,by,i,j,counter)]+q\n",
    "                        visited.add((bx,by,i,j))\n",
    "            if abs(bx-px)+abs(by-py)==1:\n",
    "                for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                    if px+dx==bx and py+dy==by:\n",
    "                        if 0<=bx+dx<m and 0<=by+dy<n and grid[bx+dx][by+dy]!=\"#\" and (bx+dx,by+dy,px+dx,py+dy) not in visited:\n",
    "                            q.append((bx+dx,by+dy,px+dx,py+dy,counter+1))\n",
    "                            visited.add((bx+dx,by+dy,px+dx,py+dy))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid):\n",
    "        def is_valid(node):\n",
    "            x, y = node\n",
    "            return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'B':\n",
    "                    box = (i, j)\n",
    "                elif grid[i][j] == 'T':\n",
    "                    target = (i, j)\n",
    "                elif grid[i][j] == 'S':\n",
    "                    men = (i, j)\n",
    "\n",
    "        que = deque([(men, box, 0)])\n",
    "        visited = {(men, box)}\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        while que:\n",
    "            men, box, d = que.popleft()\n",
    "            if box == target:\n",
    "                return d\n",
    "            for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                men_temp = (men[0] + i, men[1] + j)\n",
    "                if is_valid(men_temp):\n",
    "                    if men_temp == box:\n",
    "                        box_temp = (box[0] + i, box[1] + j)\n",
    "                        if is_valid(box_temp) and (men_temp, box_temp) not in visited:\n",
    "                            que.append((men_temp, box_temp, d + 1))\n",
    "                            visited.add((men_temp, box_temp))\n",
    "                    elif (men_temp, box) not in visited:\n",
    "                        que.appendleft((men_temp, box, d))\n",
    "                        visited.add((men_temp, box))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid):\n",
    "        def is_valid(node):\n",
    "            x, y = node\n",
    "            return 0 <= x < m and 0 <= y < n and grid[x][y] != '#'\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'B':\n",
    "                    box = (i, j)\n",
    "                elif grid[i][j] == 'S':\n",
    "                    men = (i, j)\n",
    "\n",
    "        que = deque([(men, box, 0)])\n",
    "        visited = {(men, box)}\n",
    "        while que:\n",
    "            men, box, d = que.popleft()\n",
    "            if grid[box[0]][box[1]] == 'T':\n",
    "                return d\n",
    "            for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                men_temp = (men[0] + i, men[1] + j)\n",
    "                if not is_valid(men_temp):\n",
    "                    continue\n",
    "                if men_temp == box:\n",
    "                    box_temp = (box[0] + i, box[1] + j)\n",
    "                    if not is_valid(box_temp) or (men_temp, box_temp) in visited:\n",
    "                        continue\n",
    "                    que.append((men_temp, box_temp, d + 1))\n",
    "                    visited.add((men_temp, box_temp))\n",
    "                elif (men_temp, box) not in visited:\n",
    "                    que.appendleft((men_temp, box, d))\n",
    "                    visited.add((men_temp, box))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPushBox(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'T':\n",
    "                    ti,tj = (i,j)\n",
    "                elif grid[i][j] == 'S':\n",
    "                    si,sj = (i,j)\n",
    "                elif grid[i][j] == 'B':\n",
    "                    bi,bj = (i,j)\n",
    "        drt = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        q.append(((si,sj),(bi,bj),0))\n",
    "        visited = set()\n",
    "        visited.add(((si,sj),(bi,bj)))\n",
    "        def check(i,j):\n",
    "            return 0<=i<m and 0<=j<n and grid[i][j] !='#'\n",
    "        while q:\n",
    "            (si,sj),(bi,bj),step = q.popleft()\n",
    "            if (bi,bj) == (ti,tj):\n",
    "                return step\n",
    "            for dx,dy in drt:\n",
    "                sx,sy = si+dx,sj+dy\n",
    "                if not check(sx,sy):\n",
    "                    continue\n",
    "                if (sx,sy) == (bi,bj):\n",
    "                    bx,by = bi+dx,bj+dy\n",
    "                    if check(bx,by) and((sx,sy),(bx,by)) not in visited:\n",
    "                        q.append(((sx,sy),(bx,by),step+1))\n",
    "                        visited.add(((sx,sy),(bx,by)))\n",
    "                elif ((sx,sy),(bi,bj)) not in visited:\n",
    "                    q.appendleft(((sx,sy),(bi,bj),step))\n",
    "                    visited.add(((sx,sy),(bi,bj)))\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
